package exercises.leetcode;

import exercises.newcoder.util.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * <a href="https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/">
 * 剑指 Offer 32 - III. 从上到下打印二叉树 III</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
 * <p>
 * 例如:
 * <p>
 * 给定二叉树: [3,9,20,null,null,15,7],
 * <pre>{@code
 *    3
 *   / \
 *  9  20
 * / \
 * 15  7
 *  }</pre>
 * 返回其层次遍历结果：
 * <pre>{@code
 * [
 *      [3],
 *      [20,9],
 *      [15,7]
 * ]
 *  }</pre>
 * 提示：
 * <p>
 * 节点总数 <= 1000
 *
 * @author or2
 * @date 2021年09月29日 时间: 18:42
 */
public class Offer32$3 {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null)
            return new ArrayList<>();
        /* 辅助数据 */
        Deque<TreeNode> deque = new LinkedList<>();
        TreeNode last = root;
        byte evenOrOdd = 1;
        /* 存储辅助数据 */
        List<List<Integer>> res = new ArrayList<>();
        LinkedList<Integer> layer = new LinkedList<>();

        /* 层序遍历 */
        deque.addLast(root);
        while (true) {
            TreeNode first = deque.removeFirst();
            /* 单数正向插入数据, 偶数逆向插入数据 */
            if ((evenOrOdd & 1) == 1)
                layer.addLast(first.val);
            else
                layer.addFirst(first.val);

            if (first.left != null)
                deque.addLast(first.left);
            if (first.right != null)
                deque.addLast(first.right);

            /* 是否是最后一个元素 */
            if (first == last) {
                evenOrOdd++;
                res.add(layer);
                layer = new LinkedList<>();
                /* 更新下一行的最后一个元素 */
                if (!deque.isEmpty())
                    last = deque.getLast();
                else
                    break;
            }
        }

        return res;
    }

    //定义列表
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> levelOrderQuickerVersion(TreeNode root) {
        //奇数的从左到右，偶数的从右到左
        helper(root, 0);
        return res;
    }

    private void helper(TreeNode root, int level) {
        if (root == null) {
            return;
        }

        if (res.size() == level) {
            res.add(new LinkedList<>());
        }

        if (level % 2 == 0) {
            //偶数，从右到左
            res.get(level).add(root.val);
        } else {
            ((LinkedList<Integer>) (res.get(level))).addLast(root.val);
        }

        helper(root.left, level + 1);
        helper(root.right, level + 1);
    }
}
